package com.practice.niuke.new_direct_basics.class02;

/**
 * 给你一个整数数组，并且这个数组是按递增排序的，
 * 你要找到数组中的两个整数，它们的和等于给定的目标值，
 * 然后返回它们的下标。
 *
 * 题目假设给你的数组总是有且只有一个解，而且同一个元素不能使用两次。
 * 另外，返回结果的下标要从 1 开始。
 *
 * @author lineng
 * @create 2020-02-07 13:56
 */
public class AlgoCasts {
    /**
     * 双指针遍历求解。
     * Time: O(n), Space: O(1)
     *
     * @param numbers 所给的数组
     * @param target 所给的目标值
     * @return int[]
     */
    public int[] getTwoNumSumToGivenValue(int[] numbers, int target) {
        // 用两个指针分别指向数组的起始和结束位置, i=0, j=numbers.length-1
        int i = 0, j = numbers.length - 1;
        // 遍历数组i<j时（同一个元素不能使用两次）
        while (i < j) {
            // 若 numbers[i] + numbers[j] > target, 故j向左移动一位，再做判断
            if (numbers[i] + numbers[j] > target) --j;
            // 若 numbers[i] + numbers[j] < target, 故i向右移动一位，再做判断
            else if (numbers[i] + numbers[j] < target) ++i;
            // 若 numbers[i] + numbers[j] == target
            else return new int[]{i + 1, j + 1};
        }
        return new int[]{-1, -1};
    }
}
